package com.hfb.mashibing.alip8.diamondsquarealgorithm.class11;

import java.util.Stack;

/** 动态规划：
 *      给你一个栈，请你在不申请额外的数据结的前提下，
 *      构逆序这个栈的元素？
 *
 *      ① 递归
 *      ② 动态规划
 *
 */
public class Code04_ReverseStackUsingRecursive {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>(){{
            push(1);
            push(2);
            push(3);
            push(4);
            push(5);
            push(6);
        }};
        System.err.printf("{src:%s}\n", stack);
        reverse(stack);
        System.err.printf("{reverse(rsc):%s}\n", stack);
    }

    /**
     * 去底后返回————返回去掉栈底元素后的新栈
     * @param stack
     */
    public static void reverse(Stack<Integer> stack){
        if(stack.isEmpty()) return;
        int i = f(stack);
        reverse(stack);
        stack.push(i);
    }
    /**
     * 去底后返回————返回去掉栈底元素后的新栈
     * @param stack
     */
    public static int f(Stack<Integer> stack){
        int result = stack.pop();
        if (stack.isEmpty())
            return result;
        else {
            int last = f(stack);
            stack.push(result);
            return last;
        }
    }



}
